\begin{chapter}{Aritm\'etica de la computadora}
\chaptermark{Artim\'etica Finita}

La computadora usa aritm\'etica de d\'igitos finitos. Esto implica que 
todo n\'umero representable tiene un n\'umero de d\'igitos fijo y 
finito. 
La representaci\'on de un n\'umero depende de la base elegida $\beta$, 
la cantidad de d\'igitos de la mantisa $t$, y los l\'imites $l$ y $u$ 
del exponente.

\begin{displaymath}
	\displaystyle x^* = \pm\; (0,d_1 d_2 \ldots d_t) \times \beta^e
\end{displaymath}

Donde $0 \leq d_i < \beta$, $l \leq e \leq u$ y $d_1 \neq 0$ (esta 
\'ultima condici\'on le da el nombre de representaci\'on de punto 
flotante \emph{normalizada}). 
El n\'umero $0$ es tratado como un caso especial.

\paragraph{}
Para todo n\'umero representado vale que $\beta^{l - 1} < m 
\leq |x^*| \leq M = (1 - \beta^{-t}) \times \beta^u$. 
De encontrarse fuera del rango $[m,M]$ entonces se dice que ocurri\'o 
\textsl{underflow} u \textsl{overflow}.

\par
Cabe destacar que, como puede verse en la figura, los n\'umeros de 
m\'aquina no est\'an uniformemente distribuidos, sino que se encuentran 
m\'as concentrados para valores pequeños.

\begin{figure}[H] \centering
	\subfloat{\includegraphics[scale=.30]{images/pfdensidad.png}}
	\caption{N\'umeros normalizados cuando $\beta = 2, \; l = -1, 
				\; u = 2$.}
\end{figure}

\begin{definition}
	El error de redondeo unitario, o $\varepsilon$ de la m\'aquina, es 
	aquel valor tal que $\displaystyle |\delta| \leq \varepsilon = 
	\frac{1}{2}\beta^{-t+1}$, siendo $\delta$ aquel valor que verifica 
	$x^* = x(1+\delta)$. Asimismo, $\varepsilon$ determina el menor 
	n\'umero tal que $1+\varepsilon \neq 1$.
\end{definition}

\begin{definition}
	Los errores relativos y absolutos de una aproximaci\'on $p^*$ de 
	$p$ se definen respectivamente como
	\begin{eqnarray*}
		\varepsilon_r(p) & = & \frac{|p - p^*|}{|p|} \\
		\varepsilon_{abs}(p) & = & |p - p^*|
	\end{eqnarray*}
\end{definition}

\begin{definition}
	El n\'umero $p^*$ aproxima $p$ con $t$ d\'igitos significativos si 
	$t$ es el entero no negativo m\'as grande para el cual 
	$\displaystyle \varepsilon_{r}(p) < \frac{1}{2}\beta^{-t+1}$.
\end{definition}

\begin{theorem}
	Todos los n\'umeros reales pueden ser representados con $t$ 
	d\'igitos significativos con un \emph{error relativo} que no 
	supera el error de redondeo unitario siendo
	\begin{eqnarray*}
		& \displaystyle \beta^{-t+1}, & 
				\textrm{si se usa truncamiento} \\
		& \displaystyle \frac{1}{2}\beta^{-t+1}, 
				& \textrm{si se usa redondeo}
	\end{eqnarray*}
\end{theorem}

Dentro de los c\'alculos que m\'as problemas traen al trabajar con 
aritm\'etica finita se encuentra la sustracci\'on de n\'umeros casi 
iguales, conocida como \textbf{cancelaci\'on catastr\'ofica}, la cual 
genera la supresi\'on de d\'igitos significativos en el resultado.

Otro c\'alculo que intenta evitarse fuertemente es la divisi\'on por 
n\'umeros pequeños, puesto que un error m\'inimo en el dividendo se 
traduce en uno mucho mayor en el resultado. La falta de precisi\'on 
podr\'ia ocasionar un overflow o p\'erdida de d\'igitos significativos.

\begin{example}
	La estrategia de pivoteo (parcial o total) para el algoritmo de 
	eliminaci\'on gaussiana apunta a evitar este \'ultimo problema 
	buscando siempre el n\'umero m\'as grande por el que se pueda 
	dividir. Dado que los n\'umeros de punto flotante est\'an m\'as 
	concentrados cerca del cero entonces al dividir por un n\'umero 
	m\'as grande es m\'as probable conseguir una mejor aproximaci\'on.
\end{example}

Otro problema com\'un es que el hecho de sumar un n\'umero grande a 
uno pequeño puede hacer que el pequeño desaparezca. En ciertos casos 
esto no ocasiona un problema ya que, si se tiene un n\'umero de gran 
magnitud probablemente se pueda considerar al m\'as pequeño 
despreciable. 

\par
Debe tenerse mucho cuidado con el orden de las operaciones ya que si, 
por ejemplo, se suma una gran cantidad de numeros pequeños entre ellos 
(que juntos tienen un peso considerable) y luego se lo suma a un 
n\'umero grande todo funcionar\'a correctamente; pero si se van sumando 
uno por uno los n\'umeros pequeños al grande entonces en cada paso el 
n\'umero pequeño ser\'a considerado despreciable y se llegar\'a a un 
resultado err\'oneo.

\begin{definition}
	Un problema est\'a \textbf{mal condicionado} cuando pequeños 
	cambios en los datos de entrada producen grandes cambios en 
	la salida.
	%~ M\'as formalmente, el \textbf{n\'umero de condici\'on} de $f$ 
	%~ en $x$ es
	%~ \[ \text{cond} = \frac{|\text{cambio relativo en el output}|}
	%~ {|\text{cambio relativo en el input}|} = 
	%~ \left[  \frac{\left\Vert f(\hat x) - f(x)\right\Vert}
	%~ {\Vert f(x) \Vert} \left/ 
	%~ \frac{\Vert \hat x - x\Vert }{\Vert x \Vert} \right \right] \]
	% donde $\hat x$ es cercano a $x$, y est\'a mal condicionado 
	%~ cuando $\text{cond}$ es mucho mayor a $1$.
\end{definition}

\begin{definition}
	Un algoritmo es \textbf{inestable} si pequeños errores en alguna 
	etapa del algoritmo (por ejemplo al principio) son ampliados en 
	las etapas subsiguientes degradando seriamente el c\'alculo final.
\end{definition}

\begin{definition}
	Dado un algoritmo, los coeficientes de condici\'on y estabilidad 
	sirven para indicar cu\'an estable es dicho algoritmo.
\end{definition}

El an\'alisis de los coeficientes de condici\'on y estabilidad es 
interesante ya que permite saber si los errores de las variables 
ingresadas se amplifican, mantienen o reducen al aplicar las 
operaciones. 
La forma de calcularlos para funciones de una variable est\'a dada 
por la ecuaci\'on

\begin{equation} 
	\varepsilon(f(x)) = \frac{f'(x)}{f(x)} * x * 
			\varepsilon(x) + \varepsilon_{opf}
	%~ \label{error1var}
\end{equation}

donde $\varepsilon_{opf}$ es el error intr\'inseco de la operaci\'on 
que calcula la funci\'on $f$, los coeficientes acompañando este 
t\'ermino son los llamados \textbf{coeficientes de estabilidad} y los 
que acompañan al t\'ermino $\varepsilon(x)$ son los llamados 
\textbf{coeficientes de condici\'on}.

\begin{remark}
	Los coeficientes de \emph{condici\'on} no dependen del algoritmo 
	sino de la naturaleza del problema, y los coeficientes de 
	\emph{estabilidad} s\'i dependen del algoritmo usado para 
	resolverlo.

	Por ejemplo si el problema es calcular $A^{-1}$, el 
	condicionamiento depende solamente de $A$, no del algoritmo 
	ni de la precisi\'on de punto flotante de la computadora.
\end{remark}

%~ \begin{definition}
	%~ Se puede generalizar el concepto de la 
	%~ \textbf{F\'ormula \ref{error1var}} a varias variables, 
	%~ sea $$f(x_1,\ldots,x_n) = \otimes(x_1,\ldots,x_n)$$ donde 
	%~ $\otimes$ es la operaci\'on realizada por $f$ y las $g_i$ 
	%~ funciones de los par\'ametros de entrada, su equivalente se 
	%~ define de la siguiente manera
	%~ \begin{equation}
		%~ \varepsilon(f(x_1,\ldots,x_n)) = 
			%~ \left( \sum_{i=1}^n \frac{\delta f}{\delta x_i} * 
			%~ \frac{1}{f(x_1,\ldots,x_n)} * x_i * 
			%~ \varepsilon(x_i) \right) + \varepsilon_\otimes
	%~ \end{equation}
%~ \end{definition}

%~ \begin{example}
	%~ Sea $f(x,y) = x + (xy)$, el desarrollo del error utilizando la 
	%~ definición quedar\'ia
	%~ \begin{eqnarray*}
		%~ \varepsilon(f(x,y)) & = & \frac{\delta f}{\delta x} * 
		%~ \frac{1}{x + xy} * x * \varepsilon(x) + 
		%~ \frac{\delta f}{\delta y} * \frac{1}{x + xy} * (xy) * 
		%~ \varepsilon(x * y) + \varepsilon_+ \\
		%~ & = & \frac{1 + y}{x + xy} * x * \varepsilon(x) + 
		%~ \frac{x}{x + xy} * (xy) * \varepsilon(x * y) + 
		%~ \varepsilon_+ \\
		%~ & = & \varepsilon(x) + \frac{1}{1 + y} * (xy) * 
		%~ \varepsilon(x * y) + \varepsilon_+
	%~ \end{eqnarray*}
	%~ Ahora debe calcularse el error de realizar $g(x,y) = x*y$
	%~ 
	%~ \begin{eqnarray*}
		%~ \varepsilon(g(x,y)) & = & \frac{\delta g}{\delta x} * 
		%~ \frac{1}{xy} * x * \varepsilon(x) + \frac{\delta g}{\delta y} 
		%~ * \frac{1}{xy} * y * \varepsilon(y) + \varepsilon_* \\
		%~ & = & \frac{yx}{xy} * \varepsilon(x) + \frac{xy}{xy} * 
		%~ \varepsilon(y) + \varepsilon_* \\
		%~ & = & \varepsilon(x) + \varepsilon(y) + \varepsilon_*
	%~ \end{eqnarray*}%
%~ 
	%~ reemplazando 
	%~ 
	%~ \begin{eqnarray*}
		%~ \varepsilon(f(x,y)) & = & \varepsilon(x) + 
		%~ \frac{1}{1 + y} * (xy) * (\varepsilon(x) + \varepsilon(y) 
		%~ + \varepsilon_*) + \varepsilon_+ \\
		%~ & = & \varepsilon(x) + \frac{xy}{1 + y} * (\varepsilon(x) 
		%~ + \varepsilon(y) + \varepsilon_*) + \varepsilon_+
	%~ \end{eqnarray*}
%~ \end{example}

\end{chapter}
